package com.example.sprintbootarithmetic.arithmeic;

import java.util.ArrayList;
import java.util.List;

public class Binarysearch {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 1000, 2000,2000,2000, 4000};
        int[] arr2={0,23,125,1241251,1251};
    }
    /**
    * 在同一个数组中，有多个相同的值，找出并获得他们的索引（我的做法:为顺序寻找，循环次数过多）
    * @description:
     * @param arr
     * @param left
     * @param right
     * @param var
    * @return: List<Integer>
    * @author: daixingyu
    * @date: 2022-01-29  22:25
    */
    public static List<Integer> birryarray(int[] arr, int left, int right, int var) {
        int mid = (left + right) / 2;
        int findvar = arr[mid];
        if (findvar > var) {
            birryarray(arr, left, mid + 1, var);
        } else if (findvar < var) {
            birryarray(arr, left, mid - 1, var);
        } else {
            ArrayList list = new ArrayList();
            list.add(mid);
            int temp = mid ;
            while (temp >= 0) {
                int tempvar = temp;
                if (arr[tempvar] == var&&tempvar!=mid) {
                    list.add(tempvar);
                }
                temp--;
            }
            int temp2 = mid;
            while (temp2 <= arr.length - 1) {
                int tempvar = temp2;
                if (arr[tempvar] == var&&tempvar!=mid) {
                    list.add(tempvar);
                }
                temp2++;
            }
            return list;
        }
        return null;
    }

    /**
    * 老师的做法:循环次数变少
    * @description:
    * @return: null
    * @author: daixingyu
    * @date: 2022-01-29  23:22
    */
    public static List<Integer> birryarray2(int[] arr, int left, int right, int var){
        int mid=(left+right)/2;
        int findvar=arr[mid];
        if(findvar>var){
            birryarray2(arr,left,mid-1,var);
        } else if (findvar < var) {
            birryarray2(arr,left,mid+1,var);
        }else{
            List<Integer> arrayList=new ArrayList<>();
            arrayList.add(mid);
            int temp=mid-1;
            while(true){
                if(temp<0||arr[temp]!=findvar){
                    break;
                }
                arrayList.add(temp);
                temp--;
            }
            temp=mid+1;
            while(true){
                if(temp>arr.length-1||arr[temp]!=findvar){
                    break;
                }
                arrayList.add(temp);
                temp++;
            }
            return arrayList;
        }
        return  null;
    }
}
